package com.wp.InterviewAlgorithm.lesson1;

/**
 * Created by 王萍 on 2017/8/25 0025.
 */

/**
 * 给定两个链表，分别表示两个非负整数。它们的数字逆序存储在链表中，且每个节点
 * 只存储一个数字，计算两个数字的和，返回和的链表的头指针。注意：和也是逆序存放的。
 * 如：输入：2->4->3,5->6->4，输出：7->0->8。
 */
public class 链表相加 {

    private static class Node {
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }

        public Node() {
        }
    }

    public static void main(String[] args) {
//        Node before1 = new Node(3);
//        Node before2 = new Node(2);
//        Node before3 = new Node(1);
//        before1.next = before2;
//        before2.next = before3;
//
//        Node after1 = new Node(6);
//        Node after2 = new Node(5);
//        Node after3 = new Node(4);
//        after1.next = after2;
//        after2.next = after3;

        Node before1 = new Node(4);
        Node before2 = new Node(9);
        Node before3 = new Node(0);
        Node before4 = new Node(4);
        Node before5 = new Node(7);
        Node before6 = new Node(1);
        before1.next=before2;
        before2.next=before3;
        before3.next=before4;
        before4.next=before5;
        before5.next=before6;

        Node after1=new Node(1);
        Node after2=new Node(7);
        Node after3=new Node(1);
        Node after4=new Node(5);
        Node after5=new Node(5);
        Node after6=new Node(4);
        Node after7=new Node(2);
        Node after8=new Node(8);
        after1.next=after2;
        after2.next=after3;
        after3.next=after4;
        after4.next=after5;
        after5.next=after6;
        after6.next=after7;
        after7.next=after8;

        Node sum = sum(before1, after1);
        printNode(sum);
    }

    public static Node sum(Node before, Node after) {
        if (before == null && after == null) return null;
        if (before == null && after != null) return after;
        if (before != null && after == null) return before;

        Node result = new Node();//用于返回sum的链表。
        Node current = result;       //在sum链表生成过程中，表示当前节点。
        int carryFlag = 0;              //表示进位。
        int value;
        while (true) {
            value = before.value + after.value + carryFlag;
            carryFlag = value / 10;
            current.value = value % 10;

            before = before.next;
            after = after.next;

            if (before == null || after == null) break;   //若有一个链表遍历至结尾，就结束循环。
            current.next = new Node();
            current = current.next;
        }

        //若两个链表的长度不相等，把较长的那个链表的剩余部分拷贝到sum链表中。
        Node p = (before == null ? after : before);
        while (p != null) {
            current.next = new Node();
            current = current.next;
            current.value = p.value;
            p = p.next;
        }
        return result;
    }

    public static void printNode(Node node) {
        StringBuilder builder = new StringBuilder("");
        while (node != null) {
            builder.append(node.value).append("->");
            node = node.next;
        }
        System.out.println(builder.substring(0, builder.length() - 2));
    }
}
